package datastructure;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 *
 * @author lzy
 * @create 2019-11-20 下午1:43
 */
public class Chapter5_11 {

    public static void main(String[] args) {
        int w = 10;
        int[] p = {5, 5, 3, 4, 3};
        int[] g = {400, 500, 200, 300, 350};
        System.out.println("---------v0----------");
        System.out.println("最优收益为:" + getBestGodMining(w, p.length, p, g));
        System.out.println("最优收益为:" + getBestGodMining(w, p, g));
        System.out.println("最优收益为:" + getBestGodMiningV2(w, p, g));
    }

    /**
     * 获得金矿最优受益,采用递归的方式
     * 复杂度是O(2^n)
     *
     * @param w 　工人数量
     * @param n 　可选金矿数量
     * @param p 　金矿开采所需的工人数量
     * @param g 　金矿储量
     * @return
     */
    public static int getBestGodMining(int w, int n, int[] p, int[] g) {
        if (w == 0 || n == 0) {
            return 0;
        }

        if (w < p[n - 1]) {
            return getBestGodMining(w, n - 1, p, g);
        }

        return Math.max(getBestGodMining(w, n - 1, p, g), getBestGodMining(w - p[n - 1], n - 1, p, g) + g[n - 1]);
    }

    /**
     * 采用表格法自底向上求解动态规划问题
     * <p>
     * 时间复杂度和空间复杂度都是O(nw)
     *
     * @param w 　工人数量
     * @param p 　金矿开采需要的工人数量
     * @param g 　金矿储量
     * @return
     */
    public static int getBestGodMining(int w, int[] p, int[] g) {
        System.out.println("-------v1-------");
        //1.创建表格
        int[][] resultTable = new int[p.length + 1][w + 1];
        //2.填充表格
        for (int i = 1; i <= p.length; i++) {
            for (int j = 1; j <= w; j++) {
                if (j < p[i - 1]) {
                    resultTable[i][j] = resultTable[i - 1][j];
                } else {
                    resultTable[i][j] = Math.max(resultTable[i - 1][j], resultTable[i - 1][j - p[i - 1]] + g[i - 1]);
                }
            }
            System.out.println(Arrays.toString(resultTable[i]));
        }

        return resultTable[p.length][w];
    }

    public static int getBestGodMiningV2(int w, int[] p, int[] g) {
        System.out.println("-------v2-------");
        //1.创建表格
        int[] resultTable = new int[w + 1];
        //2.填充表格
        //　ｉ表示金矿，j表示工人数
        for (int i = 1; i <= p.length; i++) {
            //　注意要从右向左计算
            for (int j = w; j >= 1; j--) {
                if (j >= p[i - 1]) {
                    resultTable[j] = Math.max(resultTable[j], resultTable[j - p[i - 1]] + g[i - 1]);
                }
            }
            System.out.println(Arrays.toString(resultTable));
        }
        return resultTable[w];
    }
}
